//
//  main.c
//  Demo
//
//  Created by aron on 16/10/9.
//  Copyright © 2016年 aron. All rights reserved.
//

#include <stdio.h>

// malloc exit
#include <stdlib.h>

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType* elem;///<开始位置
    int length;///<长度
    int listsize;///<容量
}Sqlist;

void initSqlist(Sqlist* l){
    l->elem = (ElemType *)malloc(MaxSize*sizeof(ElemType));
    if (!l->elem) {
        exit(0);
    }
    l->length = 0;
    l->listsize = MaxSize;
}

// 静态顺序表插入
void insertElem1(ElemType sqlist[], int n, int i, ElemType item){
    if (n==MaxSize || i<1 || i>n+1) {
        exit(0);
    }
    int t;
    for (t = n-1; t>=i-1; t--) {
        sqlist[t+1] = sqlist[t];
    }
    sqlist[i-1] = item;
    n = n+1;
}


// 动态顺序表插入
void insertElem2(Sqlist* l, int i, ElemType item){
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>l->length+1) {
        exit(0);
    }
    if (l->length >= l->listsize) {
        base = (ElemType*)realloc(l->elem, (l->listsize+10)*sizeof(ElemType));
        l->elem = base;
        l->listsize = l->listsize+10;
    }
    
    insertPtr = &(l->elem[i-1]);
    for (p=&(l->elem[l->length-1]); p>=insertPtr; p--) {
        *(p+1) = *p;
    }
    *insertPtr = item;
    l->length ++;
}

// 动态顺序表插入
void insertElem3(Sqlist l, int i, ElemType item){
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>l.length+1) {
        exit(0);
    }
    if (l.length >= l.listsize) {
        base = (ElemType*)realloc(l.elem, (l.listsize+10)*sizeof(ElemType));
        l.elem = base;
        l.listsize = l.listsize+1000;
    }
    
    insertPtr = &(l.elem[i-1]);
    for (p=&(l.elem[l.length-1]); p>=insertPtr; p--) {
        *(p+1) = *p;
    }
    *insertPtr = item;
    l.length ++;
}

void testSqlist() {
    printf("\n======testSqlist=======\n");
    
    Sqlist l;
    initSqlist(&l);
    int i;
    for (i=1; i<=100000; i++) {
        insertElem2(&l, i, i);
//        insertElem3(l, i, i);// Error Occur
    }
    
    printf("\nThe content of the list is\n");
    for (i=0; i<l.length; i++) {
        printf("%d ", l.elem[i]);
    }
    printf("\n");
}


int bin_search(int arr[], int n, int key) {
    int lowPtr,highPtr,midPtr = 0;
    lowPtr = 0;
    highPtr = n-1;
    while (lowPtr <= highPtr) {
        midPtr = (lowPtr + highPtr)/2;
        if (arr[midPtr] == key) {
            return midPtr;
        }
        if (arr[midPtr]<key) {
            lowPtr = midPtr + 1;
        }
        if (arr[midPtr]>key) {
            highPtr = midPtr-1;
        }
    }
    return -1;
}

void test_bin_search() {
    int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int resultIndex = bin_search(arr, 20, 9);
    printf("resultIndex = %d", resultIndex);
}


/**
 insert sort asc

 @param a array
 @param n count
 */
void insert_sort_asc(int a[], int n){
    int i;
    for (i=1; i<n; i++) {
        int j = i;
        while (j>0 && a[j-1]>a[j]) {
            int tmp = a[j-1];
            a[j-1] = a[j];
            a[j] = tmp;
            j--;
        }
    }
}


/**
 insertion sort desc

 @param a array to sort
 @param n array count
 */
void insert_sort_desc(int a[], int n) {
    // 第0个位置空出来做临时的变量存储位置,访问真实数据的下标从1开始
    int i, j;
    for(i=2; i<=n; i++){
        a[0] = a[i];
        j = i-1;// 与前面j个比较
        while (j>0 && a[0]>a[j]) {
            //大于，需要把之前排序的数据往后移动,移动标记
            a[j+1] = a[j];
            j--;
        }
        // 把排序的数据放入正确的位置，j索引的后一个位置，极端的情况，第一次比较，位置i的数据比位置j的还小a[j+1] = a[i];即保持位置不变
        a[j+1] = a[0];
    }
}

#define GET_ARRAY_LEN(array) (sizeof(array) / sizeof(array[0]))

void test_insert_sort() {
    int arr[] = {8,9,10,11,1,16,17,13,19,2,3,18,4,5,6,20,712,14,15};
    insert_sort_asc(arr, 19);
    int i;
    for (i=0; i<19; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    int arr2[] = {-1, 8,9,10,11,1,16,17,13,19,2,3,18,4,5,6,20,712,14,15};
    int count = GET_ARRAY_LEN(arr2)-1;
    insert_sort_desc(arr2, count);
    for (i=1; i<=count; i++) {
        // 第一个位置去掉
        printf("%d ", arr2[i]);
    }
    printf("\n");
}

void selection_sort(int arr[], int n) {
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    // 测试动态顺序表
    // testSqlist();
    
    // 测试二分查找
//    test_bin_search();
    
    // 测试插入排序
    test_insert_sort();
    
    return 0;
}
